package Demo29;

/**
 * 除自身以外数组的乘积
 * https://leetcode.cn/problems/product-of-array-except-self/description/
 */

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] f = new int[len];
        int[] g = new int[len];
        int[] ret = new int[len];
        // 处理边界问题

        g[len - 1] = f[0] = 1;
        // 准备前缀积数组 和 后缀积数组
        for(int i = 1; i < len;i++) f[i] = f[i-1] * nums[i-1];
        for(int i = len - 2;i>=0;i--) g[i] = g[i+1] * nums[i+1];
        // 使用数组
        for(int i = 0; i < len;i++) ret[i] = f[i] * g[i];
        return ret;
    }
}
class Demo {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] ret = solution.productExceptSelf(new int[] {1,2,3,4});
        for(int n: ret) {
            System.out.print(n + " ");
        }
    }
}